题目分析

这道题目典型的找规律，为什么这么说呢？从时间复杂度上就可以看出端倪，一般从数据量上就可以看出，这个题目的数据最大为$2^31$，说明用线性复杂度的算法都会超时，那么一定有特殊的方法进行求解。

数学规律

我们一般按照位数进行找规律，0-9一位数中，只有1个1出现，而00-99中，这100个两位数中，有20个1出现，为什么呢？因为两位数的各位都是0-9，重复了10次，00-09，10-19，20-29，等等，一共10组，每一组的个位都有一个1，因此有10个，但是10-19这十个数中，十位也都是1，那么共有10 + 10 x 1 = 20个1。同理，我们可以得出000-999，这1000个三位数中，000-099，100-199，200-299，等等，一共10组，每一组的后两位都相当于00-99，因此共有10 x 20 = 200个，而且100-199，共有100个1，因此共有100 + 10 x 20 = 300个1。
根据这个规律，我们可以使用一种递归的思想，进行求解。
我以6666这个数字举例，6666可以分成6000+666因为最高位是6，因此可以看成从0-5999中所有1的个数，加上6000-6666中所有1的个数，0-5999的个数，可以从上面的规律中直接求解，0-999共有300个1，因此0-5999共有1000 + 6 * 300 = 2800个1，而6000-6666中，最高位都是6，可以看成0-666中所有的1的个数。就变成求2800 + 0-666中1的个数。再次递归，666可以分成600 + 66，0-599共有 100 + 6 * 20 = 220，因此变成求2800 + 220 + 0-66中1的个数。再次递归，66可以分成60 + 6，0-59共有10 + 6 + 1 = 16，因此变为2800 + 220 + 16 + 0-6中1的个数。再次递归，0-6中只有1个，总数为2800 + 220 + 16 + 1 = 3037个。
再举一个复杂一点的例子6106，6106可以分成6000 + 106，可以看成0-5999中所有1的个数共有2800个1，加上6000-6106中所有1的个数，因此变成求2800 + 0-106中1的个数。再次递归，106可以分成100 + 6，可以看成0-99中所有1的个数，加上100-106中所有1的个数，0-99中1的个数为20，因为没有超过200，所以不能加100，而且100-106中最高位是1，因此不能看成0-6中1的个数，而是要加上100-106中数字的个数，因为每一个数字的最高位都是1。这样就可以看成0-6中1的个数，因此为2800 + 20 + (106 - 100) + 1 + 0-6中1的个数，等于2828个。
因为一位数也满足这个条件，因此可以将一位数也放入该情形，不需要单独进行讨论，所以可以得到下面的代码。时间复杂度为$O(log(n))$，空间复杂度为$O(log(n))$。

class Solution:
    res = 0
    def countDigitOne(self, n):
        lens = len(str(n))
        one_num = [0] * lens
        for i in range(1, lens):
            one_num[i] = one_num[i - 1] * 10 + 10 ** (i - 1)
        self.res = 0
        
        def sub_question(n):
            if n == 0:
                return
            array = [int(x) for x in str(n)]
            lens = len(array)
            high = 10 ** (lens - 1)
            if array[0] == 1:
                self.res += n - high + 1 + one_num[lens - 1]
            elif array[0] != 0:
                self.res += high + one_num[lens - 1] * array[0]
            sub_question(n - high * array[0])
        
        sub_question(n)
        return self.res

刷题总结

这个题目还是比较有趣的，难度较大，很多同学采用暴力法进行遍历统计1的个数，那么时间复杂度为$O(n \times log(n))$，在数据量很大的时候，是不合适的。这道题是不是非常有趣呢，小伙伴们务必掌握它。